package leetCode;

/**
 * 740. 删除并获得点数
 * https://leetcode.cn/problems/delete-and-earn/description/
 */
class Solution1 {
    public int deleteAndEarn(int[] nums) {
        // int n = 10001;//题目中说明了nums最大值是1w，所以可以直接创建一个足够大的数组，而不用在nums找到最大值，再创建最大值大小的数组
        // int[] newNums = new int[10001];
        int n = 0;
        for(int i = 0; i < nums.length; i++) {
            n = Math.max(n, nums[i]);
        }
        int[] newNums = new int[n + 1];
        for(int x : nums) newNums[x] += x;
        //求newNums能获得最大点数，转换成打家劫舍问题，删（偷）完当前元素，相邻的元素不能删（偷）
        //创建dp表
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        //初始化
        f[0] = newNums[0];
        g[0] = 0;
        //填表
        for(int i = 1; i < n + 1; i++) {
            f[i] = g[i - 1] + newNums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        //返回值
        return Math.max(f[n], g[n]);
    }
//    public static int deleteAndEarn(int[] nums) {
//        int len = nums.length;
//        int max = 0;
//        for (int i = 0; i < len; i++) {
//            max = Math.max(max, nums[i]);
//        }
//        int[] newNums = new int[max + 1];
//        for(int i = 0; i < len; i++) {
//            newNums[nums[i]]++;
//        }
//        //求newNums能获得最大点数，转换成打家劫舍问题，删（偷）完当前元素，相邻的元素不能删（偷）
//        //创建dp表
//        int[] f = new int[max + 1];
//        int[] g = new int[max + 1];
//        //初始化表
//        f[1] = newNums[1];
//        g[1] = 0;//可不写
//        for(int i = 2; i < max + 1; i++) {
//            f[i] = g[i - 1] + newNums[i] * i;
//            g[i] = Math.max(g[i - 1], f[i - 1]);
//        }
//        //返回值
//        return Math.max(f[max], g[max]);
//    }
}